package algotithm.weekendrace.leetcode239.test3;

/**
 * @author 25068
 * @Date 2021/5/2 10:27
 * @Title 5746. 到目标元素的最小距离
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
//        String num = "5489355142";
        String num = "11112";
        int k = 4;
        int minSwaps = solution.getMinSwaps(num, k);
        System.out.println(minSwaps);
    }


    public int getMinSwaps(String num, int k) {
        char[] c = num.toCharArray();
        char[] ori = num.toCharArray();
        int n = c.length, cnt = 0;
        for(int i = 0; i < k; i++) {
            nextPermutation(c);
        }
        for(int i = 0; i < n; i++) {
            if(ori[i] == c[i]) {
                continue;
            }
            for(int j = i + 1; j < n; j++) {
                if(ori[j] == c[i]){
                    for(int tt = j; tt > i; tt--) {
                        swap(ori, tt - 1, tt);
                        cnt++;
                    }
                    break;
                }
            }
        }
        return cnt;
    }

    public void nextPermutation(char[] nums) {
        int i = nums.length - 2;
        // 从后往前找找到一个非递增的
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            // 找到第一个比之前找到的nums[i]大的
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            // 交换
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    private void reverse(char[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(char[] nums, int i, int j) {
        char temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
